import java.util.*;
class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

public class Test {
    // 题目 1：平衡二叉树
    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }

        return height(root) >= 0;
    }

    private int height(TreeNode root){
        if(root == null){
            return 0;
        }

        int left = height(root.left);
        if(left < 0){
            return -1;
        }

        int right = height(root.right);
        if(right < 0){
            return -1;
        }

        if(Math.abs(left - right) < 2){
            return left > right ? left + 1 : right + 1;
        }else{
            return -1;
        }
    }

    // 题目 2：将有序数组转换为二叉搜索树
    // 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
    //
    //高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
    public TreeNode sortedArrayToBST(int[] nums) {
        return BST(nums, 0, nums.length - 1);
    }

    private TreeNode BST(int[] nums, int left, int right){
        if(left > right){
            return null;
        }

        int mid = (left + right) / 2;

        TreeNode tree = new TreeNode(nums[mid]);

        tree.left = BST(nums, left, mid - 1);
        tree.right = BST(nums, mid + 1, right);

        return tree;
    }

    // 题目 3：将二叉搜索树变平衡
    // 给你一棵二叉搜索树，请你返回一棵 平衡后 的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。如果有多种构造方法，请你返回任意一种。
    //
    //如果一棵二叉搜索树中，每个节点的两棵子树高度差不超过 1 ，我们就称这棵二叉搜索树是 平衡的 。
    List<Integer> list = new ArrayList<>();

    public TreeNode balanceBST(TreeNode root) {
        getInorder(root);
        return BST(0, list.size() - 1);
    }

    private void getInorder(TreeNode root){
        if(root == null){
            return;
        }
        getInorder(root.left);
        list.add(root.val);
        getInorder(root.right);
    }

    private TreeNode BST(int left, int right){
        if(left > right){
            return null;
        }
        int mid = (left + right) / 2;
        TreeNode tree = new TreeNode(list.get(mid));
        tree.left = BST(left, mid - 1);
        tree.right = BST(mid + 1, right);
        return tree;
    }

    // 题目4：完全二叉树的节点个数
    // 给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
    //
    //完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
    public int countNodes(TreeNode root) {
        if(root == null){
            return 0;
        }

        int left = countHeight(root.left);
        int right = countHeight(root.right);

        if(left == right){
            return countNodes(root.right) + (1 << left);
        }else{
            return countNodes(root.left) + (1 << right);
        }
    }

    private int countHeight(TreeNode root){
        int height = 0;
        while(root != null){
            height++;
            root = root.left;
        }
        return height;
    }


    Thread


}
